#include <cstdlib>
#include <iostream>
#include "Node.h"

template <typename T>
class LinkedList
{
private:
    Node<T>* head;
public:
    LinkedList();
    ~LinkedList();
    void append(const Node<T>& _node);
    void append(T _val);
    void list() const;
    void headback(); //move head back one place
    T pop_front();
    Node<T>* find(T _val) const; //return the address of the previous node of
                                 //the first node containing the _val,and return
                                 //NULL if it dose not exist.
    void del(Node<T>* _add); //delete the node next to the node whose address
                             //is _add.
    void insert(T _val); //add a node to store _val,and keep the order
    

};

template <typename T>
LinkedList<T>::LinkedList()
{
    head = NULL;
};

template <typename T>
LinkedList<T>::~LinkedList()
{
    if (head != NULL)
    {
	Node<T>* p = head;
	while (p->get_next() != NULL)
	{
	    Node<T>* t = p;
	    p = p->get_next();
	    delete t;
	}
	delete p;
    }
};

template <typename T>
void LinkedList<T>::append(const Node<T>& _node)
{
    Node<T>* tail = head;
    Node<T>* p = new Node<T>;
    p->set_data(_node.get_data());
    p->set_next(NULL);
    if (tail != NULL)
    {
    while (tail->get_next() != NULL)
	tail = tail->get_next();
    tail->set_next(p);
    }
    else
	head = p;
};

template <typename T>
void LinkedList<T>::append(T _val)
{
    Node<T>* tail = head;
    Node<T>* p = new Node<T>;
    p->set_data(_val);
    p->set_next(NULL);
    if (tail != NULL)
    {
    while (tail->get_next() != NULL)
	tail = tail->get_next();
    tail->set_next(p);
    }
    else
	head = p;
};

template <typename T>
void LinkedList<T>::list() const
{
    Node<T>* tail = head;
    if (tail != NULL)
    {
	while (tail->get_next() != NULL)
	{
	    std::cout << tail->get_data() << ", ";
	    tail = tail->get_next();
	}
	std::cout << tail->get_data() << std::endl;
    }
};

template <typename T>
T LinkedList<T>::pop_front()
{
    if (head == NULL)
    {
	std::cerr << "Error! Can not pop a data from an empty list." << std::endl;
	return -1;
    }
    Node<T>* p = head;
    T data = p->get_data();
    head = p->get_next();
    delete p;
    return data;
};

template <typename T>
void LinkedList<T>::headback(){
    head=head->get_next();
}


template <typename T>
Node<T>* LinkedList<T>::find(T _val) const
{
    Node<T>* p = head;
    if (p == NULL) //Empty list
	return NULL;
    if (p->get_data() == _val) //The first node is to find,create q to point
    {                          //to it.
	Node<T> *q =new Node<T>;
	q->set_next(p);
	return q;
    }
    while (p->get_next() != NULL)
    {
      if (p->get_next()->get_data() == _val)
	return p;
      p = p->get_next();
    }
    return NULL;
}


template <typename T>
void LinkedList<T>::del(Node<T>* _add){
  if (_add->get_next()==head) // The first node is to delete.
    headback();	//move head back one place
  else{	
    if (_add->get_next()==NULL)
      std::cout << "no element to delete!" << std::endl;
    else if (_add->get_next()->get_next()==NULL) //The last node is to be delete.
    {
     Node<T> *p=new Node<T>;
     p->set_next(_add->get_next());
     _add->set_next(NULL);
     delete p;
    }
    else{
     Node<T> *p=new Node<T>;
     p->set_next(_add->get_next());
     _add->set_next(_add->get_next()->get_next());
     delete p;
    }
  }
}

template <typename T>
void LinkedList<T>::insert(T _val){
  Node<T> *p=new Node<T>;
  p=(*this).find(_val);
  if (p==NULL) //New element,added at the end.
    (*this).append(_val);
  else
  {  
    p = p->get_next();
    while(p->get_next() != NULL && p->get_next()->get_data() == p->get_data())
      p = p->get_next();
    if (p->get_next() == NULL)// add to the end
      (*this).append(_val);
    else{
      Node<T> *q=new Node<T>; //create node q to insert _val
      q->set_data(_val);
      q->set_next(p->get_next());
      p->set_next(q);
    }
  } 
}
